package algorithm;

import java.awt.Point;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

public class ImprovedNlognDistanceFinder extends AbstractDistanceFinder {

	Random random = new Random();

	public Point[] findMinimumDistance(Point[] points) {
		quicksort_x(points);
		Point[] pair = new Point[2];
		findMinimumDistance(points, 0, points.length, pair);

		return pair;
	}

	private double findMinimumDistance(Point[] pts, int start, int end,
			Point[] pair) {
		double distance = 0;
		if (end - start <= 100) {
			return findMinDistance(pts, start, end, pair);
		}
		int middle = (start + end) / 2;
		int axisX = pts[middle].x;
		Point[] pair1 = new Point[2];
		Point[] pair2 = new Point[2];
		double d1 = findMinimumDistance(pts, start, middle, pair1);
		double d2 = findMinimumDistance(pts, middle, end, pair2);
		if (d1 <= d2) {
			distance = d1;
			pair[0] = pair1[0];
			pair[1] = pair1[1];
		} else {
			distance = d2;
			pair[0] = pair2[0];
			pair[1] = pair2[1];
		}
		// collect the points beside the line x = axisX
		// find the bounds.
		int p = middle, r = middle;
		while (p >= 0 && (axisX - pts[p].x) <= distance)
			p--;
		p++;
		while (r < end && (pts[r].x - axisX) <= distance)
			r++;
		// copy points into another array;
		Point[] tmppts = new Point[r - p];
		for (int i = p; i < r; i++) {
			tmppts[i - p] = pts[i];
		}
		// sort y
		quicksort_y(tmppts);

		// calc distances
		for (int i = 0; i < tmppts.length; i++) {
			for (int j = i + 1; j < i + 7 && j < tmppts.length; j++) {
				double d = calcDistance(tmppts[i], tmppts[j]);
				if (d < distance) {
					distance = d;
					pair[0] = tmppts[i];
					pair[1] = tmppts[j];
				}
			}
		}
		return distance;
	}

	private double findMinDistance(Point[] points, int start, int end,
			Point[] pair) {
		double distance = Double.MAX_VALUE;
		double tmpDistance = 0;
		for (int i = start; i < end - 1; i++) {
			for (int j = i + 1; j < end; j++) {

				tmpDistance = calcDistance(points[i], points[j]);
				if (tmpDistance < distance) {
					distance = tmpDistance;
					pair[0] = points[i];
					pair[1] = points[j];
				}
			}
		}
		return distance;
	}

	public void quicksort_x(Point[] pts) {
		quicksort_x(pts, 0, pts.length - 1);
	}

	private void quicksort_x(Point[] pts, int left, int right) {
		if (left >= right)
			return;

		int index = left + random.nextInt(right - left + 1);
		Point tmp = pts[index];
		swap(pts, index, right);
		for (int i = index = left; i < right; ++i) {
			if (pts[i].x <= tmp.x) {
				swap(pts, index++, i);
			}
		}
		swap(pts, index, right);
		quicksort_x(pts, left, index - 1);
		quicksort_x(pts, index + 1, right);
	}

	public void quicksort_y(Point[] pts) {
		quicksort_y(pts, 0, pts.length - 1);
	}

	private void quicksort_y(Point[] pts, int left, int right) {
		if (left >= right)
			return;
		int index = left + random.nextInt(right - left + 1);
		Point tmp = pts[index];
		swap(pts, index, right);
		for (int i = index = left; i < right; ++i) {
			if (pts[i].y <= tmp.y) {
				swap(pts, index++, i);
			}
		}
		swap(pts, index, right);
		quicksort_y(pts, left, index - 1);
		quicksort_y(pts, index + 1, right);
	}

	private void swap(Point[] pts, int i, int j) {
		Point p = pts[i];
		pts[i] = pts[j];
		pts[j] = p;
	}

}
